{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split BST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #recursion #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #递归 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #拆分二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉搜索树（BST）的根结点 <code>root</code>&nbsp;和一个整数 <code>target</code> 。请将该树按要求拆分为两个子树：其中一个子树结点的值都必须小于等于给定的目标值；另一个子树结点的值都必须大于目标值；树中并非一定要存在值为&nbsp;<code>target</code>&nbsp;的结点。</p>\n",
    "\n",
    "<p>除此之外，树中大部分结构都需要保留，也就是说原始树中父节点 <code>p</code> 的任意子节点 <code>c</code> ，假如拆分后它们仍在同一个子树中，那么结点 <code>p</code>&nbsp;应仍为 <code>c</code>&nbsp;的父结点。</p>\n",
    "\n",
    "<p>返回 <em>两个子树的根结点的数组</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/13/split-tree.jpg\" style=\"height: 193px; width: 600px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,6,1,3,5,7], target = 2\n",
    "<strong>输出：</strong>[[2,1],[4,3,6,null,null,5,7]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [1], target = 1\n",
    "<strong>输出:</strong> [[1],[]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉搜索树节点个数在&nbsp;<code>[1, 50]</code>&nbsp;范围内</li>\n",
    "\t<li><code>0 &lt;= Node.val, target &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-bst](https://leetcode.cn/problems/split-bst/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-bst](https://leetcode.cn/problems/split-bst/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,6,1,3,5,7]\\n2', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if root==None:\n",
    "            return [None,None]\n",
    "        if root.val>target:\n",
    "            rootleft,rootright=self.splitBST(root.left,target)\n",
    "            root.left=rootright\n",
    "            return [rootleft,root]\n",
    "        else:\n",
    "            rootleft,rootright=self.splitBST(root.right,target)\n",
    "            root.right=rootleft\n",
    "            return [root,rootright]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if root is None:\n",
    "            return [None,None]\n",
    "        if root.val<=target:\n",
    "            p=self.splitBST(root.right,target)\n",
    "            root.right=p[0]\n",
    "            return [root,p[1]]\n",
    "        else:\n",
    "            p=self.splitBST(root.left,target)\n",
    "            root.left=p[1]\n",
    "            return [p[0],root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if not root:\n",
    "            return [None,None]\n",
    "        if root.val <= target:\n",
    "            L,R = self.splitBST(root.right, target)\n",
    "            root.right = L\n",
    "            return [root,R]\n",
    "        else:\n",
    "            L,R = self.splitBST(root.left, target)\n",
    "            root.left = R\n",
    "            return [L,root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def splitBST(self, root, V):\n",
    "        if not root:\n",
    "            return None, None\n",
    "        elif root.val <= V:\n",
    "            bns = self.splitBST(root.right, V)\n",
    "            root.right = bns[0]\n",
    "            return root, bns[1]\n",
    "        else:\n",
    "            bns = self.splitBST(root.left, V)\n",
    "            root.left = bns[1]\n",
    "            return bns[0], root\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if root is None:\n",
    "            return [None, None]\n",
    "\n",
    "        res = [None, None]\n",
    "        if root.val <= target:\n",
    "            res[0] = root\n",
    "            right = self.splitBST(root.right, target)\n",
    "            res[1] = right[1]\n",
    "            root.right = right[0]\n",
    "\n",
    "        else:\n",
    "            res[1] = root\n",
    "            left = self.splitBST(root.left, target)\n",
    "            res[0] = left[0]\n",
    "            root.left = left[1]\n",
    "\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        d1, d2 = TreeNode(-1), TreeNode(-1)\n",
    "        p1, p2 = d1, d2\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.val > target:\n",
    "                p2.left = cur\n",
    "                p2 = p2.left\n",
    "                cur = cur.left\n",
    "                p2.left = None\n",
    "                \n",
    "            else:\n",
    "                p1.right = cur\n",
    "                p1 = p1.right\n",
    "                cur = cur.right\n",
    "                p1.right = None\n",
    "\n",
    "        return [d1.right, d2.left]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        def dfs(root,target):\n",
    "            if not root:\n",
    "                return None,None\n",
    "            elif root.val <= target:\n",
    "                bns = dfs(root.right,target)\n",
    "                root.right = bns[0]\n",
    "                return root,bns[1]\n",
    "            else:\n",
    "                bns = dfs(root.left,target)\n",
    "                root.left = bns[1]\n",
    "                return bns[0],root\n",
    "        return dfs(root,target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        # 一个小于等于 一个大于等于\n",
    "        if root == None:\n",
    "            return [None, None]\n",
    "        node1, node2 = None, None\n",
    "        if root.val > target:\n",
    "            node1, node2 = self.splitBST(root.left, target)\n",
    "            root.left = node2\n",
    "            return [node1, root]\n",
    "        elif root.val < target:\n",
    "            node1, node2 = self.splitBST(root.right, target)\n",
    "            root.right = node1\n",
    "            return [root, node2]\n",
    "        else:\n",
    "            # 返回当前节点\n",
    "            node2 = root.right\n",
    "            root.right = None\n",
    "            node1 = root\n",
    "            return [node1, node2]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if root is None:\n",
    "            return [None, None]\n",
    "\n",
    "        res = [None, None]\n",
    "        if root.val <= target:\n",
    "            res[0] = root\n",
    "            right = self.splitBST(root.right, target)\n",
    "            res[1] = right[1]\n",
    "            root.right = right[0]\n",
    "\n",
    "        elif root.val > target:\n",
    "            res[1] = root\n",
    "            left = self.splitBST(root.left, target)\n",
    "            res[0] = left[0]\n",
    "            root.left = left[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if root is None:\n",
    "            return None, None\n",
    "        elif root.val <= target:\n",
    "            l, r = self.splitBST(root.right, target)\n",
    "            root.right = l\n",
    "            l = root\n",
    "            return l, r\n",
    "        else:\n",
    "            l, r = self.splitBST(root.left, target)\n",
    "            root.left = r\n",
    "            r = root\n",
    "            return l, r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if root is None:\n",
    "            return [None, None]\n",
    "        if root.val == target:\n",
    "            right = root.right\n",
    "            root.right = None\n",
    "            return [root, right]\n",
    "        if root.val < target:\n",
    "            left,right = self.splitBST(root.right,target)\n",
    "            root.right = left\n",
    "            return [root, right]\n",
    "        if root.val > target:\n",
    "            left,right = self.splitBST(root.left,target)\n",
    "            root.left = right\n",
    "            return [left, root]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitBST(self, root: TreeNode, target: int) -> List[TreeNode]:\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type target: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return [None, None]\n",
    "\n",
    "        res = [None, None]\n",
    "\n",
    "        if root.val <= target:\n",
    "            # root 必然是第一棵 BST 的根节点\n",
    "            res[0] = root\n",
    "            # 第二棵 BST 的根节点需要去右子树算\n",
    "            right = self.splitBST(root.right, target)\n",
    "            res[1] = right[1]\n",
    "            # 保证 root 的右子树都是小于 target 的\n",
    "            root.right = right[0]\n",
    "        else:\n",
    "            # root 必然是第二棵 BST 的根节点\n",
    "            res[1] = root\n",
    "            # 第一棵 BST 的根节点需要去左子树寻找\n",
    "            left = self.splitBST(root.left, target)\n",
    "            res[0] = left[0]\n",
    "            # 保证 root 的左子树都是大于 target 的\n",
    "            root.left = left[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if not root:\n",
    "            return None, None\n",
    "        \n",
    "        if root.val <= target:\n",
    "            root.right, greaterTree = self.splitBST(root.right, target)\n",
    "            return root, greaterTree\n",
    "        else:\n",
    "            lessTree, root.left = self.splitBST(root.left, target)\n",
    "            return lessTree, root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if not root:\n",
    "            return [None, None]\n",
    "        \n",
    "        if root.val == target:\n",
    "            right = root.right\n",
    "            root.right = None\n",
    "            return [root, right]\n",
    "\n",
    "        left, right = None, None\n",
    "        if root.val > target:\n",
    "            left, right = self.splitBST(root.left, target)\n",
    "            root.left = right\n",
    "            return [left, root]\n",
    "        else:\n",
    "            left, right = self.splitBST(root.right, target)\n",
    "            root.right = left\n",
    "            return [root, right]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if root is None:\n",
    "            return [None,None]\n",
    "        if root.val<=target:\n",
    "            p=self.splitBST(root.right,target)\n",
    "            root.right=p[0]\n",
    "            return [root,p[1]]\n",
    "        else:\n",
    "            p=self.splitBST(root.left,target)\n",
    "            root.left=p[1]\n",
    "            return [p[0],root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if root is None:\n",
    "            return [None,None]\n",
    "        if root.val<=target:\n",
    "            p=self.splitBST(root.right,target)\n",
    "            root.right=p[0]\n",
    "            return [root,p[1]]\n",
    "        else:\n",
    "            p=self.splitBST(root.left,target)\n",
    "            root.left=p[1]\n",
    "            return [p[0],root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        if not root:\n",
    "            return None, None\n",
    "        elif root.val <= target:\n",
    "            bns = self.splitBST(root.right, target)\n",
    "            root.right = bns[0]\n",
    "            return root, bns[1]\n",
    "        else:\n",
    "            bns = self.splitBST(root.left, target)\n",
    "            root.left = bns[1]\n",
    "            return bns[0], root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def splitBST(self, root, V):\n",
    "        if not root:\n",
    "            return None, None  # 左, 右\n",
    "\n",
    "        elif root.val <= V:\n",
    "            # 切分点在右侧，在右子树中寻找\n",
    "            # 最终一定是将右侧部分独立，左侧部分保留，接回root作为新的右子树\n",
    "            bns = self.splitBST(root.right, V)\n",
    "            root.right = bns[0]  # 左侧需要接回root\n",
    "            return root, bns[1]\n",
    "        else:\n",
    "            # 切分点在左侧，因此在左子树中寻找\n",
    "            # 最终一定是将左侧部分独立，右侧部分保留，接回root作为新的左子树\n",
    "            bns = self.splitBST(root.left, V)\n",
    "            root.left = bns[1]  # 右侧接回root\n",
    "            return bns[0], root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:\n",
    "        # samll, large\n",
    "        if root is None:\n",
    "            return None, None\n",
    "        elif root.val <= target:\n",
    "            right_small, right_large = self.splitBST(root.right, target)\n",
    "            root.right = right_small\n",
    "            return root,right_large\n",
    "        else:\n",
    "            left_small,left_large = self.splitBST(root.left, target)\n",
    "            root.left = left_large\n",
    "            return left_small, root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
